package lc20240520;

import java.util.Arrays;

public class Demo2 {
    public static void main(String[] args) {
        int[] postOrder={9,15,7,20,3};
        int[] inOrder={9,3,15,20,7};
        TreeNode root=buildTree(inOrder,postOrder);
        printTree(root);
    }

    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder.length == 0 || inorder.length == 0) {
            return null;
        }
        int len= postorder.length;
        int rootValue = postorder[len-1];
        TreeNode root = new TreeNode(rootValue);

        int mid = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (postorder[len-1]==inorder[i]){
                mid=i;
                break;
            }
        }
        //构建左子树前序后序遍历
        int[] arrayInLeft=Arrays.copyOfRange(inorder,0,mid);
        int[] arrayPostLeft= Arrays.copyOfRange(postorder,0,mid);
        //构建右子树前序后序遍历
        int[] arrayInRight=Arrays.copyOfRange(inorder,mid+1,inorder.length);
        int[] arrayPostRight=Arrays.copyOfRange(postorder,mid,len-1);

        root.left=buildTree(arrayInLeft,arrayPostLeft);
        root.right=buildTree(arrayInRight,arrayPostRight);
        return root;
    }

    public static void printTree(TreeNode root){
        if (root!=null){
            printTree(root.left);
            System.out.println(root.val);
            printTree(root.right);
        }
    }
}
